import { cbtPrint } from "hy-algokit";

export class Heap<T> {
  private data: T[] = [];
  private length: number = 0;
  //区分是最大堆还是最小堆
  private isMax: boolean;

  constructor(arr?: T[], isMax = true) {
    this.isMax = isMax;
    arr && this.buildHeap(arr);
  }

  private compare(i: number, j: number): boolean {
    if (this.isMax) {
      return this.data[i] >= this.data[j];
    } else {
      return this.data[i] <= this.data[j];
    }
  }

  //根据索引交换数组里的数据
  private swap(i: number, j: number) {
    const temp = this.data[i];
    this.data[i] = this.data[j];
    this.data[j] = temp;
  }

  //方法
  insert(value: T) {
    //新加入的插入数组最后面
    this.data.push(value);
    this.length++;

    let index = this.length - 1;

    this.percolateUp(index);
  }

  //上滤操作
  protected percolateUp(index: number): void {
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.compare(parentIndex, index)) {
        break;
      }

      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }

  //提取  删除
  extract(): T | undefined {
    //边界判断
    if (this.length === 0) return undefined;
    if (this.length === 1) {
      this.length--;
      return this.data.shift();
    }

    //其他情况需要将最后一个元素提取top，然后进行下滤操作

    const topValue = this.data[0];
    this.data[0] = this.data.pop()!;
    this.length--;
    let index = 0;

    this.percolateDown(index);
    return topValue;
  }

  //下滤操作
  private percolateDown(index: number): void {
    while (2 * index + 1 <= this.length - 1) {
      let leftChildrenIndex = 2 * index + 1;
      let rightChildrenIndex = 2 * index + 2;

      let largerIndex = leftChildrenIndex;

      if (rightChildrenIndex < this.length && this.compare(rightChildrenIndex, leftChildrenIndex)) {
        largerIndex = rightChildrenIndex;
      }

      if (this.compare(index, largerIndex)) {
        break;
      }

      this.swap(index, largerIndex);
      index = largerIndex;
    }
  }

  peek(): T | undefined {
    return this.data[0];
  }

  size(): number {
    return this.data.length;
  }

  isEmpty() {
    return this.length === 0;
  }

  buildHeap(arr: T[]) {
    this.data = arr;
    this.length = arr.length;
    let start = Math.floor((this.length - 1) / 2);
    //下滤操作
    for (let i = start; i >= 0; i--) {
      this.percolateDown(i);
    }
  }

  print() {
    cbtPrint(this.data);
  }
}

const arr = [9, 11, 20, 56, 23, 45];
const heap = new Heap<number>(arr, false);
// heap.buildHeap(arr);
heap.print();

export {};
